﻿#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    // 354. 俄罗斯套娃信封问题
    int maxEnvelopes(vector<vector<int>>& envelopes)
    {
        sort(envelopes.begin(), envelopes.end(), [&](const vector<int>& v1, const vector<int>& v2)
            {
                return v1[0] != v2[0] ? v1[0]<v2[0] : v1[1]>v2[1];
            });

        vector<int> ret;
        ret.push_back(envelopes[0][1]);
        for (int i = 1; i < envelopes.size(); ++i)
        {
            int b = envelopes[i][1];
            if (b > ret.back())
            {
                ret.push_back(b);
            }
            else
            {
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int mid = (left + right) / 2;
                    if (ret[mid] >= b)
                        right = mid;
                    else
                        left = mid + 1;
                }
                ret[left] = b;
            }
        }
        return ret.size();
    }

    // 1262. 可被三整除的最大和
    int maxSumDivThree(vector<int>& nums)
    {
        const int INF = 0x3f3f3f3f;
        int sum = 0, x1 = INF, x2 = INF, y1 = INF, y2 = INF;
        for (auto x : nums)
        {
            sum += x;
            if (x % 3 == 1)
            {
                if (x < x1)
                    x2 = x1, x1 = x;
                else if (x < x2)
                    x2 = x;
            }
            else if (x % 3 == 2)
            {
                if (x < y1)
                    y2 = y1, y1 = x;
                else if (x < y2)
                    y2 = x;
            }
        }

        if (sum % 3 == 0)
            return sum;
        else if (sum % 3 == 1)
            return max(sum - x1, sum - y1 - y2);
        else
            return max(sum - x1 - x2, sum - y1);
    }
};

int main()
{
    /*vector<vector<int>> v{ {5,4},{6,4},{6,7},{2,3} };
    cout << Solution().maxEnvelopes(v) << endl;*/

    vector<int> v{ 3,6,5,1,8 };
    cout << Solution().maxSumDivThree(v) << endl;

    return 0;
}